//////////////////////////////////////////////////
// Big Integer of LMath                         //
// Copyright@ GPL v2 Made by YXJIANG & YANGJZ   //
//////////////////////////////////////////////////


#ifndef _BIGINTEGER_OF_MATH_COPYRIGHT_GPL_V2_MADE_BY_YXJIANG_AND_YANGJZ_HPP_INC__CPLUSPLUS
#define _BIGINTEGER_OF_MATH_COPYRIGHT_GPL_V2_MADE_BY_YXJIANG_AND_YANGJZ_HPP_INC__CPLUSPLUS

#include <cstring>
#include <string>
#include <iostream>

#include <cassert>

#define COM_B ((unsigned char)10)
#define COM_L ((unsigned char)0)

namespace _LMath {

// Base Big Integer
using namespace std;

class _BigInteger {
    
    public:

    // Initialize an empty integer
    _BigInteger() : length(1), symbol(false), maxlength(8) {
        bits = new unsigned char[maxlength];
        for (unsigned long i=0; i<maxlength; ++i)
            bits[i] = 0;
    }

    // Initialize with other one integer
    _BigInteger(const _BigInteger &_rhs) : length(_rhs.length), symbol(_rhs.symbol), maxlength(_rhs.maxlength) {
        bits = new unsigned char[maxlength];
        for (unsigned long i=0; i<maxlength; ++i)
        	bits[i] = 0;
        for (unsigned long i=0; i<length; ++i)
            bits[i] = _rhs.bits[i];
    }

	// Initialize with a short integer
	_BigInteger(long i) : length(1), symbol(false), maxlength(8) {
		bits = new unsigned char[1];
		reset(i);
	}

	// Another
	_BigInteger(int i) : length(1), symbol(false), maxlength(8) {
		bits = new unsigned char[1];
		reset((long)i);
	}

    // Read an integer from the string
    _BigInteger(const char* _str) {
        bits = new unsigned char[1];
		reset(_str);
    }
    
    // Read an integer from the string object
    _BigInteger(string _str) {
        bits = new unsigned char[1];
		reset(_str.c_str());
    }

    // Destructor
    virtual ~_BigInteger() {
        delete[] bits;
    }

    //protected:

    // The datas of every bit
    unsigned char* bits;

    // The length of the integer
    unsigned long length;

    // The max length of the buffer
    unsigned long maxlength;

    // The symbol of the integer. 'false' means + and 'true' means -
    bool symbol;

    public:

    _BigInteger& operator = (const _BigInteger &_rhs) {
        delete[] bits;
        maxlength = _rhs.maxlength;
        length = _rhs.length;
        symbol = _rhs.symbol;
        bits = new unsigned char[maxlength];
        for (unsigned long i=0; i<length; ++i)
            bits[i] = _rhs.bits[i];
        return *this;
    }
    
    virtual void move(long distance) {
    	if (distance > 0) {
    		rightRange(length+distance+1);
    		for (unsigned long i=length+distance-1; i>=distance; --i) {
    			bits[i] = bits[i-distance];
			}
			for (unsigned long i=distance-1; i>0; --i) {
				bits[i] = 0;
			}
			bits[0] = 0;
			length += distance;
		} else if (distance < 0) {
			for (unsigned long i=0; i<length+distance+1; ++i) {
				bits[i] = bits[i-distance];
			}
			for (unsigned long i=length+distance+1; i<length; ++i) {
				bits[i] = 0;
			}
			length -= distance;
		}
	} 

	virtual void reset(const char *_str) {
		if (_str == NULL) {
            bits = new unsigned char[maxlength];
            bits[0] = 0;
        } else {
            int slen = strlen(_str); 
            maxlength = slen*4;
            length = 0;
            bits = new unsigned char[maxlength];
            memset(bits,0,maxlength);
            if(_str[0] == '-'){
                symbol = true;
                --slen;
                ++_str;
            } else{
                symbol = false;
            }
            while(_str[0] == '0'){
            	if (_str[1] == '\0') {
            		break;
            	} else {
                	++_str;
            	}
            }
            int i;
            slen = strlen(_str);
            for(i=0; i<slen; ++i){
                bits[i] = _str[slen-i-1]-'0';
            }
            length = slen;
        }
	}

    virtual void reset(long n) {
        delete[] bits;
        bits = NULL;
        if (n < 0) symbol = true, n = -n;
        else symbol = false;
        long i;
        unsigned long q = 0;
        length = 0;
        for (i=1; i<=n; i*=10, ++length);
        if (length == 0) ++length;
        bits = new unsigned char[maxlength = length*2];
        for (i=0; i<maxlength; ++i)
        	bits[i] = 0;
        for (i=1; i<=n; i*=10, ++q) {
            int x = n%(i*10)/i;
            bits[q] = (unsigned char)x;
        }
    }

    virtual void rightRange(unsigned long len) {
        if (len > maxlength) {
            maxlength = len*2;
            unsigned char* temp = new unsigned char[maxlength];
            for (unsigned long i=0; i<maxlength; ++i)
                if (i<length) temp[i] = bits[i];
                else temp[i] = 0;
            delete[] bits;
            bits = temp;
        }
    }
    
    public:

    virtual _BigInteger operator += (const _BigInteger &_rhs) {
		if (_rhs.symbol != symbol) {
			_BigInteger tmp1(*this), tmp2(_rhs);
			if (symbol) {
				tmp1.symbol = false;
				return *this = tmp2 - tmp1;
			} else {
				tmp2.symbol = false;
				return *this = tmp1 - tmp2;
			}
		}
		unsigned long maxx = length;
		if (_rhs.length > maxx) maxx = _rhs.length;
        rightRange(maxx + 1);
        for (unsigned long i=0; i < _rhs.length; ++i){
            bits[i] += _rhs.bits[i];
            bits[i+1] += bits[i] / COM_B;
            bits[i] %= COM_B;
        }
        for(unsigned long i = _rhs.length; bits[i] >= COM_B;++i){
            bits[i+1] += bits[i] / COM_B;
            bits[i] %= COM_B;
        }
        length = maxx + 1;
        while (bits[length] == 0 && length >= 1) --length;
        ++length;
        return *this;
    }
    
    virtual _BigInteger operator -= (const _BigInteger &_rhs) {
        if (_rhs.symbol != symbol) {
    		_BigInteger tmp(_rhs);
    		tmp.symbol = symbol;
    		return operator += (tmp);
    	} else {
    		if (symbol) {
                _BigInteger tmp1(*this), tmp2(_rhs);
                tmp1.symbol = tmp2.symbol = false;
                return *this = tmp2-tmp1;
            } else if (*this < _rhs) {
                _BigInteger tmp1(*this), tmp2(_rhs);
                tmp2.operator -=(tmp1);
                tmp2.symbol = !tmp2.symbol;
                return *this = tmp2;
            }
    	}
        unsigned char d = 0;
        for (unsigned long i=0; i<length; ++i) {
        	unsigned char subber = d;
        	if (i < _rhs.length) {
        		subber += _rhs.bits[i];
        	}
            if (subber>bits[i]) {
                bits[i] += COM_B;
                bits[i] -= subber;
                d = 1;
            } else {
                bits[i] -= subber;
                d = 0;
            }
        }
        while (bits[length-1] == 0 && length>1) --length;
        return *this;
    }
    
    virtual _BigInteger operator *= (const _BigInteger &_rhs) {
        symbol = (_rhs.symbol != symbol);
        rightRange(_rhs.length + length + 1);
        for (unsigned long i=length; i>0; --i) {
            unsigned char mulx = bits[i-1];
            bits[i-1] = COM_L;
            for (unsigned long j=0; j<_rhs.length; ++j) {
                bits[i+j-1] += mulx*_rhs.bits[j];
                for (unsigned long start=i+j-1; bits[start]>=COM_B; ++start) {
                    bits[start+1] += bits[start]/COM_B;
                    bits[start] %= COM_B;
                }
            }
        }
        length = _rhs.length+length+1;
        while (bits[length] == 0 && length >= 1) --length;
        ++length;
        return *this;
        /*
        symbol = _rhs.symbol != symbol;
        rightRange(_rhs.length + length + 1);
        unsigned long tlength = length + _rhs.length - 1;
		for (unsigned long i=length; i>0; --i) {
			for (unsigned long j=0; j<_rhs.length; ++j) {
				bits[i+j-1] += bits[i-1]*_rhs.bits[j];
				bits[i+j] += bits[i+j-1]/COM_B;
				bits[i+j-1] %= COM_B;
			}
		}
		while (tlength>1 && bits[tlength] == 0) --tlength;
		length = tlength;
        return *this;
        */
    }
    
    virtual _BigInteger operator /= (const _BigInteger &_rhs) {
    	if (_rhs.operator ==(0)) {
    		throw exception();
		}
    	symbol = (_rhs.symbol != symbol);
    	if (*this < _rhs) {
    		reset(0l);
		} else {
			_BigInteger result, level(COM_L+1);
			level.move(length-_rhs.length);
			while (*this >= _rhs) {
				while (*this >= (_rhs*level)) {
					*this -= (_rhs*level);
					result += level;
				}
				level.move(-1);
			}
        	*this = result;
		}
        return *this;
    }
    
    virtual _BigInteger operator %= (const _BigInteger &_rhs) {
    	if (_rhs.operator ==(0)) {
    		throw exception();
		}
        symbol = (_rhs.symbol != symbol);
    	if (*this >= _rhs) {
			_BigInteger result, level(COM_L+1);
			for (unsigned long bit=0; _rhs.length+bit<length; ++bit) {
				level.move(1);
			}
			while (*this >= _rhs) {
				while (*this >= (_rhs*level)) {
					*this -= (_rhs*level);
					result += level;
				}
				level.move(-1);
			}
		}
        return *this;
    }
    
    virtual _BigInteger operator ++ () {
		*this += 1;
		return *this;
    }
    
    virtual _BigInteger operator ++ (int) {
        _BigInteger old(*this);
		*this += 1;
        return old;
    }
    
    virtual _BigInteger operator -- () {
		_BigInteger temp(1);
		operator -= (temp);
		return *this;
    }
    
    virtual _BigInteger operator -- (int) {
        _BigInteger old(*this);
		_BigInteger temp(1);
		operator -= (temp);
        return old;
    }
    
    virtual bool operator < (const _BigInteger &_rhs) const{
        if (symbol != _rhs.symbol) {
            if (bits[0] == _rhs.bits[0] && bits[0] == 0 && length == _rhs.length && length == 1)
                return false;
            else return symbol;
        }
        if (length != _rhs.length) return length < _rhs.length;
        for (unsigned long i=length; i>0; --i)
            if (bits[i-1] != _rhs.bits[i-1]) {
                return symbol || (bits[i-1] < _rhs.bits[i-1]);
            }
        return false;
    }
    
    virtual bool operator == (const _BigInteger &_rhs) const{
        return (!operator <(_rhs)) && (!_rhs.operator <(*this));
    }
    
    virtual bool operator <= (const _BigInteger &_rhs) const{
        return *this < _rhs || *this == _rhs;
    }
    
    virtual bool operator > (const _BigInteger &_rhs) const{
        return !(*this <= _rhs);
    }
    
    virtual bool operator >= (const _BigInteger &_rhs) const{
        return !(*this < _rhs);
    }
    
    virtual bool operator != (const _BigInteger &_rhs) const{
        return !(*this == _rhs);
    }
    
    public:
    
    virtual _BigInteger operator + (const _BigInteger &_rhs) const{
        return _BigInteger(*this) += _rhs;
    }
    
    virtual _BigInteger operator - (const _BigInteger &_rhs) const{
        return _BigInteger(*this) -= _rhs; 
    }
    
    virtual _BigInteger operator * (const _BigInteger &_rhs) const{
        return _BigInteger(*this) *= _rhs;
    }
    
    virtual _BigInteger operator / (const _BigInteger &_rhs) const{
        return _BigInteger(*this) /= _rhs;
    }
    
    virtual _BigInteger operator % (const _BigInteger &_rhs) const{
        return _BigInteger(*this) %= _rhs;
    }
    
    public:
   
    virtual string ToString() const {
        string str;
        if(symbol){
        	if (length != 1 || bits[0] != 0) {
            	str += '-';
        	}
        }
        
        for(unsigned long i = length-1 ; ; --i){
			if (i == 0) {
				str += bits[i] + '0';
				break;
			}
            str += bits[i] + '0';
        }
        
        return str;
    }
    
    friend ostream& operator << (ostream&, const _BigInteger&);
    friend istream& operator >> (istream&, _BigInteger&);
    
    friend bool operator < (long _lhs, const _BigInteger &_rhs);
    friend bool operator > (long _lhs, const _BigInteger &_rhs);
    friend bool operator <= (long _lhs, const _BigInteger &_rhs);
    friend bool operator >= (long _lhs, const _BigInteger &_rhs);
    friend bool operator == (long _lhs, const _BigInteger &_rhs);
    friend bool operator != (long _lhs, const _BigInteger &_rhs);
    
};

ostream& operator << (ostream& out, const _BigInteger &bt) {
	return (out << bt.ToString());
}

istream& operator >> (istream& in, _BigInteger &bt) {
	string data;
	in >> data;
	bt.reset(data.c_str());
	return in;
}

bool operator < (long _lhs, const _BigInteger &_rhs) {
	return _rhs > _lhs;
}

bool operator > (long _lhs, const _BigInteger &_rhs) {
	return _rhs < _lhs;
}

bool operator <= (long _lhs, const _BigInteger &_rhs) {
	return _rhs >= _lhs;
}

bool operator >= (long _lhs, const _BigInteger &_rhs) {
	return _rhs <= _lhs;
}

bool operator == (long _lhs, const _BigInteger &_rhs) {
	return _rhs == _lhs;
}

bool operator != (long _lhs, const _BigInteger &_rhs) {
	return _rhs != _lhs;
}

#ifdef _LARGE_NUM

// Large Big Integer can save your number with lesser bits
// If your number is very big

class BigInteger : public _BigInteger {

};

#else

// The common Big Integer
// It can save your number well if your number is not very big

typedef _BigInteger BigInteger;

#endif

}

#endif
